/*
 * @lc app=leetcode.cn id=118 lang=cpp
 *
 * [118] 杨辉三角
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int> > result;        // 保存最终的结果
        vector<int> currRow;                // 记录当前行的数据

        // 如果输入为 0，直接返回
        if (numRows == 0) {
            return result;
        }

        // 生成第一行，并保存到最终结果中
        currRow.push_back(1);
        result.push_back(currRow);
        
        // 依次生成每一行数据，并保存到最终结果中
        for (int i =1; i < numRows; i++) {
            currRow.clear();
            vector<int> lastRow = result[result.size() - 1];
            
            // 构造当前行的数据
            currRow.push_back(lastRow[0]);
            for (int j = 0; j < lastRow.size() - 1; j++) {
                currRow.push_back(lastRow[j] + lastRow[j + 1]);
            }
            currRow.push_back(lastRow[0]);
            
            result.push_back(currRow);
        }
        

        return result;
    }
};
// @lc code=end

